﻿#include <iostream>
#include <vector>
#include <stack>
using namespace std;

typedef vector<vector<int>> maze_t;

// 迷宫地图的属性
enum MAZE_ATTR
{
	MAZE_WALL = 0,
	MAZE_SPACE = 1,
	MAZE_ENTRANCE = 2,
	MAZE_EXIT = 3,
	MAZE_ISVISIT = 4,
	MAZE_ROAD = 5,
	MAZE_ROW = 10,
	MAZE_COL = 10
};

// 保存迷宫位置信息的类
class MazePos
{
public:
	MazePos(int i, int j)
		: row(i),
		  col(j)
	{
	}
	int row;
	int col;
};

/*
	硬核构造一个迷宫
	数组值为0表示墙，无法通过
	数组值为1表示空地，可以通过
	数组值为2表示入口
	数组值为2表示出口
	0 0 0 0 0 0 0 0 0 0
	0 2 1 0 1 1 1 0 1 0
	0 1 1 0 1 1 1 0 1 0
	0 1 1 1 1 0 0 1 1 0
	0 1 0 0 0 1 1 1 1 0
	0 1 1 1 0 1 1 1 1 0
	0 1 0 1 1 1 0 1 1 0
	0 1 0 0 0 1 0 0 0 0
	0 0 1 1 1 1 1 1 3 0
	0 0 0 0 0 0 0 0 0 0
*/
maze_t build_maze()
{
	maze_t maze(MAZE_ROW);
	for (int i = 0; i < maze.size(); ++i)
		maze[i].resize(MAZE_COL, 0);
	// 从终端读取地图数据，并记入maze数组
	for (int i = 0; i < MAZE_ROW; ++i)
		for (int j = 0; j < MAZE_COL; ++j)
			cin >> maze[i][j];
	return maze;
}

/*打印二维数组*/
void print_2darray(const vector<vector<int>> vv)
{
	for (int i = 0; i < MAZE_ROW; ++i)
	{
		for (int j = 0; j < MAZE_COL; ++j)
			cout << vv[i][j] << " ";
		cout << endl;
	}
}

/*打印迷宫*/
void print_maze(const maze_t &maze)
{
	for (int i = 0; i < MAZE_ROW; ++i)
	{
		for (int j = 0; j < MAZE_COL; ++j)
		{
			if (MAZE_ROAD == maze[i][j])
			{
				cout << "+ ";
				continue;
			}
			if (MAZE_ENTRANCE == maze[i][j])
			{
				cout << "i ";
				continue;
			}
			if (MAZE_EXIT == maze[i][j])
			{
				cout << "e ";
				continue;
			}
			if (MAZE_WALL == maze[i][j])
				cout << "* ";
			else
				cout << "  ";
		}
		cout << endl;
	}
}

/*
	获得入口坐标
*/
MazePos get_entrance(const maze_t &maze)
{
	for (int i = 0; i < MAZE_ROW; ++i)
		for (int j = 0; j < MAZE_COL; ++j)
			if (MAZE_ENTRANCE == maze[i][j])
				return MazePos(i, j);
}

/*
	进入迷宫，输出新的迷宫地图，并在内部标注从入口到出口的路径
*/
maze_t walk_maze(const maze_t &mz)
{
	maze_t maze = mz;
	stack<MazePos> st;
	// 入口进栈
	MazePos entrance = get_entrance(maze);
	st.push(entrance);
	while (!st.empty()) // 开始dfs
	{
		// 当前位置
		MazePos cur = st.top();
		int row = cur.row;
		int col = cur.col;
		if (MAZE_EXIT == maze[row][col]) // 到达出口
		{
			break;
		}
		// 尝试往四个方向走
		if (MAZE_WALL != maze[row - 1][col] && MAZE_ISVISIT != maze[row - 1][col]) // 上
		{
			if (MAZE_EXIT != maze[row - 1][col])
				maze[row - 1][col] = MAZE_ISVISIT;
			st.push(MazePos(row - 1, col));
			continue;
		}
		else if (MAZE_WALL != maze[row][col + 1] && MAZE_ISVISIT != maze[row][col + 1]) // 右
		{
			if (MAZE_EXIT != maze[row][col + 1])
				maze[row][col + 1] = MAZE_ISVISIT;
			st.push(MazePos(row, col + 1));
			continue;
		}
		else if (MAZE_WALL != maze[row + 1][col] && MAZE_ISVISIT != maze[row + 1][col]) // 下
		{
			if (MAZE_EXIT != maze[row + 1][col])
				maze[row + 1][col] = MAZE_ISVISIT;
			st.push(MazePos(row + 1, col));
			continue;
		}
		else if (MAZE_WALL != maze[row][col - 1] && MAZE_ISVISIT != maze[row][col - 1]) // 左
		{
			if (MAZE_EXIT != maze[row][col - 1])
				maze[row][col - 1] = MAZE_ISVISIT;
			st.push(MazePos(row, col - 1));
			continue;
		}
		else // 走不通，则回溯
		{
			st.pop();
			continue;
		}
	}
	// dfs结束，利用栈内的位置信息依次将路径绘制出来
	while (!st.empty())
	{
		int row = st.top().row;
		int col = st.top().col;
		if (MAZE_EXIT != maze[row][col])
			maze[row][col] = MAZE_ROAD;
		maze[entrance.row][entrance.col] = MAZE_ENTRANCE;
		st.pop();
	}
	return maze;
}

int main()
{
	maze_t maze = build_maze();
	cout << "原地图：" << endl;
	// print_2darray(maze);
	print_maze(maze);
	maze_t new_maze = walk_maze(maze);
	cout << "走过的地图：" << endl;
	// print_2darray(new_maze);
	print_maze(new_maze);

	return 0;
}